package someTestExcemple.huaweiOd.container.queue;

import java.util.*;
//华为OD机试 - 模拟工作队列（Java 2025 A卷 200分）
//https://blog.csdn.net/guorui_java/article/details/146934383

//队列用来实现工作队列，保证任务的先进先出。
//mock 下一个任务来了，是先提交到任务队列，还是先执行任务
public class SimulateWorkQueue {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        // 读取第一行任务信息，以空格分割
        String[] taskStr = sc.nextLine().trim().split(" ");
        int N = taskStr.length / 2; // 任务数
        Task[] tasks = new Task[N];
        for (int i = 0; i < N; i++) {
            int submitTime = Integer.parseInt(taskStr[2 * i]);
            int execTime = Integer.parseInt(taskStr[2 * i + 1]);
            tasks[i] = new Task(submitTime, execTime);
        }
        // 读取第二行，依次为工作队列的最大长度和执行者数量
        String[] secondLine = sc.nextLine().trim().split("\\s+");
        int queueCapacity = Integer.parseInt(secondLine[0]);
        int executorCount = Integer.parseInt(secondLine[1]);

        // 工作队列：先进先出队列，用于存放等待执行的任务
        Queue<Task> workQueue = new LinkedList<>();

        // 空闲的执行者队列，编号小的优先，用小根堆实现
        PriorityQueue<Integer> freeExecutors = new PriorityQueue<>();
        for (int i = 1; i <= executorCount; i++) {
            freeExecutors.offer(i);
        }

        // 正在执行任务的执行者队列，根据任务结束时刻排序，相同结束时刻时编号小的优先
        PriorityQueue<Busy> busyExecutors = new PriorityQueue<>(new Comparator<Busy>() {
            public int compare(Busy b1, Busy b2) {
                if (b1.finishTime != b2.finishTime)
                    return b1.finishTime - b2.finishTime;
                return b1.executorId - b2.executorId;
            }
        });

        int droppedCount = 0; // 丢弃任务的数量
        int lastFinishTime = 0; // 最后一个任务完成的时刻
        int index = 0; // 当前处理任务的下标
        int currentTime = 0; // 当前时刻

        // 定义一个非常大的数作为无穷大
        final int INF = Integer.MAX_VALUE;

        // 事件模拟：直到所有任务处理完（包括正在等待、执行和未提交的任务）
        while (index < N || !workQueue.isEmpty() || !busyExecutors.isEmpty()) {
            // 下一个提交事件的时刻
            int nextSubTime = (index < N) ? tasks[index].submitTime : INF;
            // 下一个执行完成事件的时刻
            int nextFinishTime = (!busyExecutors.isEmpty()) ? busyExecutors.peek().finishTime : INF;

            // 当提交时刻和完成时刻相同时，在工作队列满的情况下优先处理完成事件
            boolean processSubmission = false;
            if (nextSubTime < nextFinishTime) {
                processSubmission = true;
            } else if (nextSubTime == nextFinishTime) {
                // 当工作队列未满时，直接提交任务，否则先处理完成事件
                if (workQueue.size() < queueCapacity)
                    processSubmission = true;
            }

            if (processSubmission) {
                // 更新当前时刻为任务提交时刻
                currentTime = nextSubTime;
                // 处理所有当前时刻的提交事件
                while (index < N && tasks[index].submitTime == currentTime) {
                    // 如果工作队列已满，则丢弃队列中最老的任务
                    if (workQueue.size() == queueCapacity) {
                        workQueue.poll();
                        droppedCount++;
                    }
                    // 将新任务加入工作队列
                    workQueue.offer(tasks[index]);
                    index++;
                }
                // 提交完毕后，空闲执行者立即从队列中取任务执行
                while (!freeExecutors.isEmpty() && !workQueue.isEmpty() && workQueue.peek().submitTime <= currentTime) {
                    int executorId = freeExecutors.poll();
                    Task task = workQueue.poll();
                    int finishTime = currentTime + task.execTime;
                    busyExecutors.offer(new Busy(finishTime, executorId));
                    // 更新最后任务完成时刻
                    lastFinishTime = Math.max(lastFinishTime, finishTime);
                }
            } else {
                // 处理完成事件，更新当前时刻为下一个完成事件的时刻
                currentTime = nextFinishTime;
                // 收集所有在当前时刻完成任务的执行者
                List<Integer> finishedExecutors = new ArrayList<>();
                while (!busyExecutors.isEmpty() && busyExecutors.peek().finishTime == currentTime) {
                    finishedExecutors.add(busyExecutors.poll().executorId);
                }
                // 将完成任务的执行者按编号从小到大排序（编号小的优先）
                Collections.sort(finishedExecutors);
                // 每个空闲执行者立即从队列中取任务执行
                for (int executorId : finishedExecutors) {
                    if (!workQueue.isEmpty() && workQueue.peek().submitTime <= currentTime) {
                        Task task = workQueue.poll();
                        int finishTime = currentTime + task.execTime;
                        busyExecutors.offer(new Busy(finishTime, executorId));
                        lastFinishTime = Math.max(lastFinishTime, finishTime);
                    } else {
                        // 如果没有任务等待，则执行者变为空闲
                        freeExecutors.offer(executorId);
                    }
                }
            }
        }
        // 按要求输出结果：最后任务完成时刻和丢弃任务数量，输出时不附带其他文字
        System.out.println(lastFinishTime + " " + droppedCount);
    }


    //任务类
    public static   class Task {
        int submitTime;
        int execTime;
        public Task(int start,int exec) {
            this.submitTime = start;
            this.execTime = exec;
        }
    }
    // 定义执行者忙碌事件类，记录执行者结束任务的时刻和执行者编号
    public static class Busy {
        int finishTime; // 执行完成的时刻
        int executorId; // 执行者编号

        public Busy(int finishTime, int executorId) {
            this.finishTime = finishTime;
            this.executorId = executorId;
        }
    }
}
